package a2;

import java.util.*;

/**
 * Parser defines a recursive decent parser for the following grammar:
 *  Program -> {VariableDefinition} {FunctionDefinition} Expr
 *  VariableDefinition -> let Identifier Expr 
 *  FunctionDefinition -> define Signature Program 
 *  Signature -> Identifier ( {Identifier} )
 *  Expr -> StringLiteral | Identifier | Application
 *  FunctionName -> Identifier | + | ~
 * that will show an expression as a syntax tree. 
 * @version 1.0
 * @author Michael Sawaya
 */
public class ParserOld
{

    private int currLocation;

    /**
     * Takes a purported expression, represented as a String, and 
     * returns a syntax tree for the string. 
     * @param input Purported expression
     * @return Syntax Tree of the expression
     */
    public OrderedTree<Token> parse(String input)
    {
        if (input == null || input.equals(""))
        {
            throw new IllegalArgumentException("Cannot parse null or empty string: " + input);
        }
        List<Token> tokenList = Token.tokenize(input);
        //sets the location in the list to 0
        currLocation = 0;
        //calls to check if the list is a program
        return checkIsProgram(nextToken(tokenList), tokenList);
    }

    /**
     * Retrieves the next token in the list. It must be called to iterate through the list
     * @param tokenList The token list
     * @return The next Token
     */
    private Token nextToken(List<Token> tokenList)
    {
        if (tokenList == null)
        {
            throw new NullPointerException("The given token list does not exist.");
        }
        if (!hasNextToken(tokenList))
        {
            throw new NullPointerException("There are no more tokens availible.");
        }
        else //retrieves the next token in the list and increments the counter
        {
            return tokenList.get(currLocation++);
        }
    }

    /**
     * Retrieves the current token in the list.
     * @param tokenList The token list
     * @return The next Token
     */
    private Token currToken(List<Token> tokenList)
    {
        if (tokenList == null)
        {
            throw new NullPointerException("The given token list does not exist.");
        }
        return tokenList.get(currLocation);
    }

    /**
     * Checks if the token list has a next element
     * @param tokenList The token list to check.
     * @return True if the token list has a next element
     */
    private boolean hasNextToken(List<Token> tokenList)
    {
        if (tokenList == null)
        {
            throw new NullPointerException("The given token list does not exist.");
        }
        //compares the counter to the list size to check if it has another token
        return tokenList.size() > currLocation;
    }

    /**
     * Checks the input list to see whether it follows the defined grammar for a program.
     * @param currToken The current token
     * @param inputList The token list
     * @return An Ordered Tree of Tokens representing the program
     */
    private OrderedTree<Token> checkIsProgram(Token currToken, List<Token> inputList)
    {
        //define the children for the final tree
        List<OrderedTree<Token>> varOutput = new LinkedList<OrderedTree<Token>>();
        List<OrderedTree<Token>> funOutput = new LinkedList<OrderedTree<Token>>();
        
        OrderedTree<Token> expTree = new OrderedTree<Token>();
        //checks for null input
        if (currToken == null || inputList == null)
        {
            throw new NullPointerException("Null parameters were given for variable definition.");
        }
        Token next = currToken;
        while (hasNextToken(inputList))
        {
            //Checks For Variable Definition
            if (next.getType().equals("let"))
            {
                varOutput.add(checkIsVariableDefinition(next, inputList));
                next = nextToken(inputList);
            }
            else
            {
                break;
            }
        }
        while (hasNextToken(inputList))
        {
            if (next.getType().equals("define"))
            {
                funOutput.add(checkIsFunctionDefinition(next, inputList));
                next = currToken(inputList);
            }
            else
            {
                break;
            }
        }
        if (next.getType().equals("apply")
                || next.getType().equals("StringLiteral")
                || next.getType().equals("Identifier"))
        {
            expTree = checkIsExpression(next, inputList);
            next = currToken(inputList);
        }
        else //since all the three possibilities for a program have been 
        //checked, the code should complain about any other output
        {
            throw new IllegalArgumentException("The input given was not "
                    + "legal in the predefined grammer at: " + next);
        }

        if (!next.getType().equals("end-of-input"))
        {
            throw new IllegalArgumentException("The program should of ended.");
        }

        //the program tree assembled
        OrderedTree<Token> varTree = new OrderedTree<Token>(new Token("variables"), varOutput);
        OrderedTree<Token> funTree = new OrderedTree<Token>(new Token("functions"), funOutput);
        List<OrderedTree<Token>> progList = new LinkedList<OrderedTree<Token>>();
        progList.add(varTree);
        progList.add(funTree);
        progList.add(expTree);
        return new OrderedTree<Token>(new Token("program"), progList);
    }

    /**
     * Checks the input list to see whether it follows the defined grammar for a variable definition.
     * @param currToken The current token
     * @param inputList The token list
     * @return An Ordered Tree of Tokens representing the Variable Definition
     */
    private OrderedTree<Token> checkIsVariableDefinition(Token currToken, List<Token> inputList)
    {
        //checks for null input
        if (currToken == null || inputList == null)
        {
            throw new NullPointerException("Null parameters were given for variable definition.");
        }
        //checks if the current token is a let
        Token let = currToken;
        if (!let.getType().equals("let"))
        {
            throw new IllegalArgumentException("Expected \"let\" token, found " + let);
        }
        //checks if the list has another token
        if (!hasNextToken(inputList))
        {
            throw new IllegalArgumentException("Token Expected to follow \"let\" Token");
        }
        //checks if the next token is an identifier
        Token identifier = nextToken(inputList);
        if (!identifier.getType().equals("Identifier"))
        {
            throw new IllegalArgumentException("Expected Identifier, found " + identifier);
        }
        //checks if the list has another token
        if (!hasNextToken(inputList))
        {
            throw new IllegalArgumentException("Token Expected to follow Identifier Token");
        }
        Token expStart = nextToken(inputList);
        OrderedTree<Token> expression = checkIsExpression(expStart, inputList);
        List<OrderedTree<Token>> children = new LinkedList<OrderedTree<Token>>();
        children.add(new OrderedTree<Token>(identifier, null));
        children.add(expression);
        OrderedTree<Token> output = new OrderedTree<Token>(let, children);
        return output;
    }

    /**
     * Checks the input list to see whether it follows the defined grammar for a function definition. 
     * @param currToken The current token
     * @param inputList The token list
     * @return  An Ordered Tree of Tokens representing the Function Definition
     */
    private OrderedTree<Token> checkIsFunctionDefinition(Token currToken, List<Token> inputList)
    {
        //checks for null input
        if (currToken == null || inputList == null)
        {
            throw new NullPointerException("Null parameters were given for function definition.");
        }
        Token define = currToken;
        if (!define.getType().equals("define"))
        {
            throw new IllegalArgumentException("Expected \"define\" token, found " + define);
        }
        Token siggy = nextToken(inputList);
        OrderedTree<Token> signature = checkIsSignature(siggy, inputList);
        Token prog = currToken(inputList);
        OrderedTree<Token> program = checkIsProgram(prog, inputList);
        List<OrderedTree<Token>> output = new LinkedList<OrderedTree<Token>>();
        output.add(signature);
        output.add(program);
        return new OrderedTree<Token>(define, output);
    }

    /**
     * Checks the input list to see whether it follows the defined grammar for an expression.
     * @param currToken The current token
     * @param inputList The token list
     * @return  An Ordered Tree of Tokens representing an expression
     */
    private OrderedTree<Token> checkIsExpression(Token currToken, List<Token> inputList)
    {
        //checks for null input
        if (currToken == null || inputList == null)
        {
            throw new NullPointerException("Null parameters were given for an expression.");
        }
        Token output = currToken;
        if (output.getType().equals("StringLiteral") || output.getType().equals("Identifier"))
        {
            return new OrderedTree<Token>(output, null);
        }
        else
        {
            return checkIsApplication(output, inputList);
        }
    }

    /**
     * Checks the input list to see whether it follows the defined grammar for a signature.
     * @param currToken The current token
     * @param inputList The token list
     * @return  An Ordered Tree of Tokens representing a signature
     */
    private OrderedTree<Token> checkIsSignature(Token currToken, List<Token> inputList)
    {
        //checks for null input
        if (currToken == null || inputList == null)
        {
            throw new NullPointerException("Null parameters were given for signature.");
        }
        Token rootIdent = currToken;
        //checks for root identifier
        if (!rootIdent.getType().equals("Identifier"))
        {
            throw new IllegalArgumentException("Expected Identifier, found " + rootIdent);
        }
        List<OrderedTree<Token>> output = new LinkedList<OrderedTree<Token>>();
        
        Token next = nextToken(inputList);
        if (next.getType().equals("("))
        {
            next = nextToken(inputList);
        }
        else
        {
            throw new IllegalArgumentException("Expected token \"(\", found " + next);
        }
        while (hasNextToken(inputList))
        {
            if (next.getType().equals("Identifier"))
            {
                output.add(new OrderedTree<Token>(next, null));
            }
            else if (next.getType().equals(")"))
            {
                nextToken(inputList);
                return new OrderedTree<Token>(rootIdent, output);
            }
            else
            {
                throw new IllegalArgumentException("Expected Identifier or \")\", found " + next);
            }
            next = nextToken(inputList);
        }
        throw new IllegalArgumentException("Illegal token found " + next);
    }

    /**
     * Checks the input list to see whether it follows the defined grammar for an application.
     * @param currToken The current token
     * @param inputList The token list
     * @return An Ordered Tree of Tokens representing an application
     */
    private OrderedTree<Token> checkIsApplication(Token currToken, List<Token> inputList)
    {
        if (currToken == null || inputList == null)
        {
            throw new NullPointerException("Null parameters were given for a function name.");
        }
        Token apply = currToken;
        System.out.println("apply = " + apply + " " + currLocation);
        if (!apply.getType().equals("apply"))
        {
            throw new IllegalArgumentException("Expected \"apply\", found " + apply);
        }
        Token funName = nextToken(inputList);
        System.out.println("funName = " + funName + " " + currLocation);
        OrderedTree<Token> funOutput = checkIsFunctionName(funName, inputList);
        Token leftParens = nextToken(inputList);
        if (!leftParens.getType().equals("("))
        {
            throw new IllegalArgumentException("Expected \"(\", found " + leftParens);
        }
        Token next = nextToken(inputList);
        List<OrderedTree<Token>> expressions = new LinkedList<OrderedTree<Token>>();
        while (hasNextToken(inputList))
        {
            if (!next.getType().equals(")"))
            {
                expressions.add(checkIsExpression(next, inputList));
            }
            else
            {
                return new OrderedTree<Token>(funOutput.getRootData(), expressions);
            }
            next = nextToken(inputList);
        }
        throw new IllegalArgumentException("Expected a token, found" + next);
    }

    /**
     * Checks the input list to see whether it follows the defined grammar for a function name.
     * @param currToken The current token
     * @param inputList The token list
     * @return An Ordered Tree of Tokens representing a function name.
     */
    private OrderedTree<Token> checkIsFunctionName(Token currToken, List<Token> inputList)
    {
        if (currToken == null || inputList == null)
        {
            throw new NullPointerException("Null parameters were given for a function name.");
        }
        String type = currToken.getType();
        if (type.equals("Identifier") || type.equals("+") || type.equals("~"))
        {
            return new OrderedTree<Token>(new Token("FunctionName", type), null);
        }
        else
        {
            throw new IllegalArgumentException("Expected Identifier, \"+\" or \"~\" token, found " + currToken);
        }
    }
}
